1. Field
The present invention relates to a device that uses vector quantization for data compression or pattern recognition and, more particularly, to a device that uses an analog switched-capacitor approach to vector quantization.
2. State of the Art
Processing, storage, and transmission of information in digital form have become widespread. The conversion of an analog information source to a digital code introduces distortion because of amplitude quantization. The most common form of amplitude quantization used today is scalar quantization. Scalar quantization is often synonymous with analog-to-digital conversion (ADC). In scalar quantization each sample of the information source is considered independently, meaning that any dependencies between samples are disregarded. In contrast, vector quantization (VQ) deals with a block or vector of samples at once, and as a result has some performance advantages as compared with scalar quantization.
VQ refers to a family of digital coding techniques that have mainly been used for data compression. VQ can be viewed as pattern matching, where input patterns or vectors are approximated by one of many stored patterns in a codebook. The resulting quantization error from such an approximation clearly depends upon how well the stored patterns, referred to as codevectors, represent the input vectors. Consequently, codebook generation requires prior knowledge of the information source and is important to the performance of VQ.
An log.sub.2 N bit scalar quantizer has N possible quantization levels, each represented by log.sub.2 N bits. A scalar quantization of a vector of dimension k results in N.sup.k possible quantization vectors, each represented by klog.sub.2 N bits. In VQ, the number of codevectors is typically much smaller than the N.sup.k possible quantization vectors because many of these vectors are not necessary for a particular input source. As a result the number of bits needed to represent the set of codevectors is typically much less than klog.sub.2 N, resulting in increased data compression.
Codebook generation for VQ is currently an active research area with several different algorithms in existence. In VQ, the source statistics are usually incorporated into the codebook generation process via a set of training vectors. The building of the codebook is based on this training set, which is to be representative of a particular information source. Codebook generation is often very time consuming, and is typically done off line prior to encoding.
One of the most commonly used techniques to generate codebooks for VQ is referred to as the LBG algorithm. This is an iterative partitioning algorithm based on the minimization of a distortion measure, and requires an initial codebook for starting. Partitioning of the training set is accomplished by associating each training vector with the corresponding closest codevector from the current codebook. New codevectors are computed as the centroids of the new partitions, or clusters, of training vectors. Iteratively updating codebooks in this fashion is continued until the improvement in the total distortion between the codevectors and the training vectors becomes negligible. This algorithm guarantees locally Optimal codebooks for VQ.
When referring to vector quantizers, a nearest neighbor vector quantizer is almost always assumed, although other possibilities exist. In a nearest neighbor vector quantizer the input vector is replaced by the codevector located nearest to the input vector in the vector space, as determined by some distortion measure. Consequently a nearest neighbor vector quantizer finds the codevector nearest to the input vector in the vector space, and then outputs the digital code of this nearest codevector. A commonly used distortion measure is the squared error distortion shown in equation (1), below: ##EQU1## where Vinput and Vcb are vectors of dimension k. In this background section and in the invention disclosure, a nearest neighbor vector quantizer is assumed when referring to a vector quantizer.
One drawback of VQ is that a very large number of codevectors are required to adequately represent many sources. In fact, codebook size and search complexity become unreasonably large for many applications in which the input source is encoded directly using one large codebook that is exhaustively searched. As a result, several techniques have been developed to reduce the hardware and computational complexity of direct full-search VQ. Two of the more common techniques are mean-removed VQ and tree-search VQ.
Mean-removed VQ (MRVQ) is a special case of product codes. Product codes refer to a family of vector quantization methods in which one large codebook is replaced by more than one smaller codebook. As a result, the vector space represented by the overall quantizer is given as the Cartesian product of smaller vector spaces, and hence the name product codes. In MRVQ, the sample mean of each input vector is computed and then subtracted from every vector component. The resulting mean removed, or residual, vector is then vector quantized. The utility of MRVQ is that the residual vectors can be adequately represented with many fewer codevectors as compared to the original image vectors. The mean of each vector is also coded and included along with each codevector index. Thus, a mean codebook and a residual codebook are used in MRVQ. Since the mean is a scalar quantity, it is scalar quantized. As a result, the mean codebook includes all of the possible quantization levels of the scalar quantizer. MRVQ can provide a significant reduction in the overall complexity of a VQ system as compared to direct VQ.
Tree-search VQ is a commonly used technique to reduce the codebook search complexity of vector quantization. Tree-search VQ relies on a tree-structured codebook including nodes and levels. Each node contains a small codebook, and the best codevector at each node determines the search path to the next lower level. Searching begins at the top node, or root, codebook of the tree and continues downward to the lowest level. The tree structure eliminates the need to search the entire codebook and results in a significant reduction in encoding complexity. The price for this reduced complexity is slightly higher distortion as compared to full-search VQ. Full-search codebook generation algorithms are altered to yield tree-structured codebooks.
A challenge in hardware implementations of vector quantizers is the large complexity required for searching codebooks. Codebooks with over 2.sup.16 codevectors are not uncommon for image compression applications. Nonetheless, vector quantization hardware has been developed for both speech and image coding. Almost all of the emphasis on VQ hardware to date has been on digital implementations.
The articles W. C. Fang, et al., "A VLSI Neural Processor for Image Data Compression Using Self-Organization Networks," IEEE Trans. on Neural Networks, pp. 506-18, Vol. 3, No. 3, May 1992; and G. T. Tuttle, et al., "A Low-Power Analog CMOS Vector Quantizer," Proc. IEEE Data Compression Conf., Snowbird Utah, pp. 410-419, April 1993, are the only published reports of analog VQ hardware implementations known to the inventor, and these hardware implementations suffer from relatively poor accuracy. The systems of both articles rely on an Euclidean distance (L2 norm) as a distortion measure. This measure requires a squaring operation that is accomplished in the systems of both articles by utilizing the square law characteristics of a metal-oxide-semiconductor (MOS) transistor. A problem with this approach is the relatively poor accuracy due to limitations of matching MOS transistors because of processing variations and thermal gradients.